%%%%%%%%%%%%%%%%%%%%%%% file typeinst.tex %%%%%%%%%%%%%%%%%%%%%%%%%
%
% This is the LaTeX source for the instructions to authors using
% the LaTeX document class 'llncs.cls' for contributions to
% the Lecture Notes in Computer Sciences series.
% http://www.springer.com/lncs       Springer Heidelberg 2006/05/04
%
% It may be used as a template for your own input - copy it
% to a new file with a new name and use it as the basis
% for your article.
%
% NB: the document class 'llncs' has its own and detailed documentation, see
% ftp://ftp.springer.de/data/pubftp/pub/tex/latex/llncs/latex2e/llncsdoc.pdf
%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%


\documentclass[runningheads,a4paper]{article}

\usepackage{amsmath,amsfonts,amssymb,amsthm,graphicx,graphics,epsf}
\usepackage{geometry} % see geometry.pdf on how to lay out the page. There's lots.

\usepackage{color,soul}


\usepackage{algorithmic}
\usepackage{algorithm}

\usepackage{hyperref}

\setcounter{tocdepth}{3}
\usepackage{graphicx}

\usepackage{url}

\newtheorem{theorem}{Theorem}[section]
\newtheorem{corollary}[theorem]{Corollary}
\newtheorem{lemma}[theorem]{Lemma}
\newtheorem{proposition}[theorem]{Proposition}
\newtheorem{observation}[theorem]{Observation}
\newtheorem{problem}[theorem]{Problem}
\newtheorem{definition}[theorem]{Definition}
\newtheorem{conjecture}[theorem]{Conjecture}
\newtheorem{question}[theorem]{Question}

\newcommand{\sep}{\ensuremath{\mathbf{c'}}} 
\newcommand{\Sep}{\ensuremath{\mathbf{C'}}}
\newcommand{\CP}{\ensuremath{C_P}}  
\newcommand{\cp}{\ensuremath{c_P}}  
%\newcommand{\tang}{\ensuremath{\mathbf{q'}}} 
\newcommand{\tang}{\ensuremath{\mathbf{\phi'}}} 


\newcommand{\marrow}{\marginpar[\hfill$\longrightarrow$]{$\longleftarrow$}}
\newcommand{\remark}[2]{\textcolor{red}{\textsc{#1 says:} \marrow\textsf{#2}}}
\newcommand{\greg}[1]{\remark{Greg}{#1}}
\newcommand{\stefan}[1]{\remark{Stefan}{#1}}
\newcommand{\luis}[1]{\remark{Luis}{#1}}

\newcommand{\red}{\color{red}}
\newcommand{\blue}{\color{blue}}

%% You may enlarge this list if necessary

\urldef{\mailsa}\path|{alfred.hofmann, ursula.barth, ingrid.haas, frank.holzwarth,|
\urldef{\mailsb}\path|anna.kramer, leonie.kunz, christine.reiss, nicole.sator,|
\urldef{\mailsc}\path|erika.siebert-cole, peter.strasser, lncs}@springer.com|    
\newcommand{\keywords}[1]{\par\addvspace\baselineskip
\noindent\keywordname\enspace\ignorespaces#1}



%%
%% Here you may place your macros using \newcommand{}{}
%%
\def\hull#1{{\text{CH}(#1)}}
\def\ch#1{{\hull{#1}}}


\begin{document}

% first the title is needed
\title{{\red \st{Dynamic}}  circle separability {\blue queries in logarithmic time}}

% the name(s) of the author(s) follow(s) next
%
% NB: Chinese authors should write their first names(s) in front of
% their surnames. This ensures that the names appear correctly in
% the running heads and the author index.
%
\author{Luis Barba$^1$\and Stefan Langerman$^2$\and Greg Aloupis$^3$}
%
%\institute{${}^1$ %%
%Posgrado en Ciencia e Ingenier\'ia de la Computaci\'on, Universidad Nacional Aut\'onoma de M\'exico\\${}^2$ %%
%Instituto de Matem\'aticas, Universidad Nacional Aut\'onoma de M\'exico}
%\paperemail{l.barba@uxmcc2.iimas.unam.mx}

%\paperemail{urrutia@matem.unam.mx}
%
% NB: a more complex sample for affiliations and the mapping to the
% corresponding authors can be found in the file "llncs.dem"
% (search for the string "\mainmatter" where a contribution starts).
% "llncs.dem" accompanies the document class "llncs.cls".
%


\maketitle


\begin{abstract}
Let $P$ be a set of $n$ points in the plane.
In this paper we study a new variant of the circular separability problem in which
a point set $P$ is preprocessed so that one can quickly answer queries of the following form:
Given a  geometric object $Q$, 
report the minimum circle containing $P$ and exluding $Q$.
Our data structure can be constructed in $O(n\log n)$ time using $O(n)$ space, 
and can be used to answer the query when $Q$ is either a circle or a convex $m$-gon in $O(\log n)$ or $O(\log n + \log m)$ time, respectively.
\end{abstract}


\section{Introduction}
%\luis{This is a copy of the introduction of the paper submitted to the Spanish meetings, therefore we need to update it with the new results. Greg, I think you heard about some new results in the field}
%
%Let $\Phi$ be a family of curves in $\mathbb{R}^2$ such that for every $\phi\in \Phi$, $\mathbb{R}^2 - \phi$ has exactly two connected components $\phi_1,\phi_2$.
%Let $P,Q$ be two subsets of $\mathbb{R}^2$. 
%We say that $P,Q$ are $\Phi$-separable, if there exists $\phi\in \Phi$, 
%such that $int(P), int(Q)$ are completely contained in $\phi_1,\phi_2$ respectively.

The planar separability problem consists of constructing, if possible, a boundary that  separates the plane into two components such that two given sets of geometric objects become isolated.
Typically this boundary is a single curve such as a line, circle or simple polygon, meaning that each component of the plane is connected.    Often there is an additional objective of minimizing some feature of the boundary, for instance the radius of a circle. This problem can be thought of as an extension of the case where only one set of geometric objects is given.  Problems such as computing the convex hull or minimum enclosing circle would fit in that category.
%Examples of geometric objects to be separated are  point sets and polygons.
%~\cite{
%Aggarwal:1985,
%DynamicCircleSeparability,
%DasJoseph:1990,
%MinimumPolygonalSeparation,
%LinearProgrammingInLinearTime}, 
%with $\Phi$ most often considered as the family of lines,  circles or simple polygons on the plane.

Probably the most classic instance of this problem is to separate two given point sets with a circle (or a line, which is equivalent to an infinitely large circle).  A separating line can be found, if it exists, using linear programing, which in the plane takes $O(n)$ time by 
Megiddo's algorithm~\cite{LinearProgrammingInLinearTime}.
%
%Anderson and Kim~\cite{DigitalDiskAndCompacness} presented  a quadratic algorithm for solving the circular separability  problem.  Bhattacharya~\cite{ComputingCircularSeparabilityOfPlanarPointSets}  improved the running time to $O(n\log n)$, and
%%%%by computing the entire region on which the separating circles may be centered. 
O'Rourke, Kosaraju and Megiddo~\cite{ComputingCircularSeparability} gave a linear-time algorithm for testing circular separability (in fact spherical separability in any fixed dimension), improving earlier bounds~\cite{ComputingCircularSeparabilityOfPlanarPointSets,DigitalDiskAndCompacness}.
%Their approach was to use the paraboloid transformation, to get an instance of a convex, quadratic minimization problem in three dimensions.
%
They also gave an $O(n\log n)$ algorithm for finding the largest separating circle and a linear time algorithm for finding the minimum separating circle.
Augustine et al~\cite{augustine-etal}  show how to preprocess a point set
so that the largest separating circle can be found in $O(\log n)$ time, for a query point.
They also obtain this bound for a preprocessed polygon that will contain the query point. 
The study of circular separability was developed because of the several applications it has in pattern recognition and image processing~\cite{SeparatingPointsByCricles,DigitalDiskAndCompacness}.
In higher dimensions, Lay~\cite{SeparationBySphericalSurfaces} introduced the idea of transforming an instance of the spherical separability problem in $\mathbb{R}^d$, 
to a linear separability problem in $\mathbb{R}^{d+1}$, 
using stereographic projection.

Still considering point sets, Edelsbrunner and Preparata~\cite{MinimumPolygonalSeparation} gave an $O(n\log n)$-time algorithm to find a separating convex polygon with minimum number of vertices. This was shown to be optimal if the optimal separator has linear size.  They also gave a $O(kn)$ algorithm to find a separator with either $k$ or $k{+}1$ vertices, where $k$ is the size of the optimal solution.  
%Megiddo showed that finding a minimal unrestricted separating polygon is NP-hard 
%%% but polynomial if the separating polygon has fixed size ...  not sure if the separating polygon must be simple or if there are other restrictions.    Leaving this out.

Boissonat et al.~\cite{boissonat-etal} gave a linear-time algorithm to report the smallest separating circle for two simple polygons, if it exists.

Aggarwal et al.~\cite{Aggarwal:1985}
%, Booth, O'Rourke Suri, Yap
gave an $O(n\log k)$-time algorithm to find the separating (convex) polygon with fewest vertices, between  two nested convex polygons. Here, $k$ is the size of the optimal separator.
Das and Joseph extended the problem to higher dimensions and 
proved that the problem of computing a separating polyhedron, 
having the minimum number of faces, 
for two nested convex polyhedra is NP-complete~\cite{DasJoseph:1990}.
%%% source for below : ~\cite{MinimumPolygonalSeparation}.
 Suri and O'Rourke~\cite{SO} gave a quadratic time algorithm to find a polygonal separator of two simple nested polygons. This was improved to $O(n\log n)$ time by Wang~\cite{Wang}.
 Wang and Chan~\cite{WangChan} gave an $O(n\log n)$ algorithm to find a minimal polygonal separator between two arbitrary simple polygons.
%%%



In some situations, the given geometric objects and separating boundary are constrained to be within some subset of the plane, such as a polygon.   For instance, Demaine et al.~\cite{8people} studied the separation of point sets by geodesic paths inside polygons.


We  left the problem of separating a given point set $P$ and a convex $m$-gon $Q$  for last, since this is the problem we deal with in this paper.  
If $P$ and $Q$ are to be separated by a line, the problem can be solved in linear time by treating $Q$ as a point set. 
Next consider separating $P$ and $Q$ by a circle. 
If the circle is to enclose $Q$, then $Q$ can be treated as a point set and the results mentioned above can be applied.
If the circle is to enclose  $P$, then it will exist only if a separating line exists.   

In this paper we show that $P$ can be preprocessed in $O(n\log n)$ time, using $O(n)$ space, so that for any given $m$-gon $Q$, we can find the smallest circle enclosing $P$ and excluding $Q$ $O(\log n+\log m)$ time.
This improves the $O(\log n\cdot\log m)$ bound in~\cite{DynamicCircleSeparability}, which is described in this paper as well.


\section{Preliminaries}%%%%%%%%%%

Let $P$ be a set of $n$ points in the plane and let $Q$ be a convex $m$-gon. 
We say that every circle containing $P$ is a {\em $P$-circle}.
We also say that a circle $C$ separates $P$ from $Q$, or simply that $C$ is a \emph{separating circle}, 
if $C$ is a $P$-circle and its interior does not intersect $Q$. 
Likewise, a \emph{separating line} is a straight line leaving the interiors of $P$ and $Q$ in different halfplanes.

Let $\Sep$ denote the minimum separating circle and let $\sep$ be its center.
Note that $\Sep$ always passes through at least two points of $P$, 
since otherwise a smaller separating circle can always be found.
In fact  $\sep$ must lie on an edge of the farthest-point Voronoi diagram  $\mathcal{V}(P)$, which is a tree with leaves at infinity.
For each point $p$ of $P$, let $R(p)$ be 
the farthest-point Voronoi region associated with $p$.

Let $\CP$ be the minimum enclosing circle of $P$. 
If  $\CP$ is constrained by three points of $P$ then 
its center, $\cp$, is at a vertex 
of $\mathcal{V}(P)$.  Otherwise $\CP$ is constrained by exactly two points of $P$ (forming its diameter),
in which case $\cp$ is on the interior of  an edge of $\mathcal{V}(P)$.
We can think of $\mathcal{V}(P)$ as a rooted tree on $\cp$.
For any given point $x$ on $\mathcal{V}(P)$ there is a unique path $T_x$ along $\mathcal{V}(P)$ joining  $\cp$ with $x$.

Given any point $y$ in the plane, 
let $C(y)$ be the minimum $P$-circle with center on $y$
and let $\rho(y)$ be the radius of $C(y)$.
Note that if $y$ belongs to $R(p)$ for some point $p$ of $P$, 
then $\rho(y)$ is given by $d(y,p)$, where $d(*,*)$ denotes the Euclidian distance between any two geometric objects.
Finally, we say that $y$ is a \emph{separating point} if $C(y)$ is a separating circle.

\section{Properties of the minimum separating circle}\label{section:Resultados}
In this section we  describe some properties of $\Sep$,
and the relationship between $\sep$ 
and the farthest-point Voronoi diagram.
These properties are not new. In fact most of the results in this section are either proved, stated, or assumed in~\cite{DynamicCircleSeparability}.

Let $\hull{P}$ denote the convex hull of $P$.
We assume that  the interiors of $Q$ and $\hull{P}$ are disjoint, 
otherwise there is no separating circle.
Also, if $Q$ and $\CP$ have disjoint interiors, 
then $\CP$ is trivially the minimum separating circle.

The following useful property of the farthest-point Voronoi diagram was mentioned
in~\cite{DynamicCircleSeparability}.   We provide a short proof.

\begin{proposition}\label{Rho is monotonic}
Let $x$ be a point on $\mathcal{V}(P)$. The function $\rho$ is monotonically 
increasing along the path $T_{x}$
starting at $\cp$.
\end{proposition}
\begin{proof}
Let $e$ be an edge of $\mathcal{V}(P)$ contained on  $R(p)\cap R(p')$, i.e. on the bisector of the points $p,p'$ in $P$.  Consider a point $y$ moving on the interior of $e$.  The circle $C(y)$ is constrained only by $p,p'$. As $d(y,p)$, or equivalently $d(y,p')$, increases, the radius of $C(y)$ also increases.   This function is convex, and in fact monotonic if $e$ does not intersect the segment joining $p,p'$.  This intersection can only occur if  $e$ happens to contain $\cp$ in its interior (specifically, at the point of intersection).  So, it is easy to see that the radius changes monotonically as one moves away from $\cp$ on $e$.   In other words, while moving from $\cp$ to $x$ on $T_x$ , at each edge the function $\rho$ behaves monotonically.  However we have not established the direction at  each edge yet.   Assume that we are at some vertex $w$ on $T_x$, and that by induction on the path $T_w$ we have increased $\rho$ monotonically away from $\cp$.  This is certainly true for the first edge, regardless of how many points constrain $\CP$, since $\CP$ is a global minimum.
As $w$ is a vertex of $\mathcal{V}(P)$, there are two other incident edges, not on $T_w$.  
We wish to contradict any claim that $\rho$ increases towards $\cp$ on either of those edges.
If such a claim were true, we could follow a decreasing path away from $\cp$ and $w$ towards a leaf,  and produce a vertex $d$ at a local minimum for $\rho$. That is because every edge incident to a leaf has $\rho$ increasing towards infinity.
The local minimum at $d$ contradicts the existence of $c_p$, since it corresponds to a circle $C(d)$ that is constrained by three points in such a way that any shift or shrinking of $C(d)$ results in a circle not containing all of $P$.
%Let $e$ be an edge of $T_x$, contained on  $R(p)\cap R(p')$, i.e. on the bisector of the points $p,p'$ in $P$.
%Consider a point $y$ moving along $e$. 
%As $d(y,p)$, or equivalently $d(y,p')$, increases, 
%the radius of $C(y)$ also increases.
%Thus, by moving the point $y$ away from $\cp$ towards $x$ along the path $T_x$, 
%we obtain that $\rho(y)$ increases monotonically on every edge along the way.
%\greg{should say that the path is monotonically moving away from $cp$}
\end{proof}
%The following observation is straightforward and shows the relation existing between separating circles and $P$-circles.

\begin{observation}\label{Relation P-circle separating circle}
Every $P$-circle contained in a separating circle is also a separating circle.
\end{observation}

The following is stated in~\cite{DynamicCircleSeparability}.  We provide a brief proof.
\begin{proposition}\label{CirculosEnSegmento}
Let $x$ and $y$ be two points in $\mathbb{R}^2$. If $z$ is a point contained in the segment $[x,y]$, 
then $C(z)\subseteq C(x)\cup C(y)$.
\end{proposition}
\begin{proof}
%Let $z$ be a point in the segment $[x,y]$. 
Let $a$ and $b$ be the two points of intersection between  $C(x)$ and $C(y)$. 
Let $r=d(a,z)=d(b,z)$ and let $C_r(z)$ be the circle with center on $z$ and radius $r$; see Figure~\ref{fig:CirculosEnSegmento}.

It is clear that $C(x)\cap C(y)\subseteq C_r(z)$ and since $P\subset C(x)\cap C(y)$,  we infer that $C_r(z)$ is a $P$-circle, therefore $C(z)\subseteq C_r(z)$. 
Furthermore, since $C_r(z)\subseteq C(x)\cup C(y)$ by construction, we conclude that $C(z)\subseteq C(x)\cup C(y)$.
\end{proof}

Observation~\ref{Relation P-circle separating circle} and Proposition~\ref{CirculosEnSegmento} imply that if $C(x)$ and $C(y)$ are both separating circles, then for every $z\in[x,y]$, $C(z)$ is also a separating circle.
{\blue Furthermore, this implies that the minimum separating circle is unique. }\greg{Why?}
\luis{If $C$ and $C'$ are both minimum separating circles with centers $c$ and $c'$, then, for every point $z$ in $[c,c']$, $C(z)$ is also a separating circle contained in $C\cup C'$ which means that it has an smaller radius.}

%%%%%%%%%%%%%%%%%%%%%%%%%Ejemplos
\begin{figure}[h]
\begin{center}
\includegraphics[width=75mm]{img/CirculosEnSegmento.pdf}
\caption{\small For every point $z\in [x,y]$ the circle $C(z)$ lies in the union of $C(x)$ and $C(y)$.} 
\label{fig:CirculosEnSegmento}
\end{center}
\end{figure}

The following is also demonstrated in~\cite{DynamicCircleSeparability}, with a reworded proof.
\begin{lemma}\label{Common Ancestor}
Let $x$ and $y$ be two separating points on $\mathcal{V}(P)$.
If $z$ is the lowest common ancestor of $x$ and $y$ in the rooted tree $\mathcal{V}(P)$, then $C(z)$ is a separating circle; moreover $\rho(z) \leq \min\{\rho(x), \rho(y)\}$.
\end{lemma}
\begin{proof}
Since $z$ is a common ancestor of $x$ and $y$, we infer from Proposition~\ref{Rho is monotonic} that $\rho(z)\leq \min\{\rho(x), \rho(y)\}$.   
What remains is to prove that $C(z)$ is a separating circle.
Suppose that $y\notin T_x$ and $x\notin T_y$, otherwise the result follows 
trivially since $y$ or $x$ will coincide with $z$.
So, let $e_x$ ({\em resp.} $e_y$) be the edge incident to $z$, on the path joining $z$ with $x$ ({\em resp.} $y$).
Consider the radial order of the edges incident to $z$ lying between $e_x$ and $e_y$. 
Let $e'$ be the edge consecutive to $e_x$ in this order.
Therefore, $e_x,e'$ and $z$ all belong to the boundary of some Voronoi region $R(p)$; see Figure~\ref{fig:CommonAncestor}.

Let $\ell_{z,p}$ be the line through $z$ and $p$. 
By the definition of  $\mathcal{V}(P)$,  $\ell_{z,p}$ intersects $R(p)$ only at the point $z$, and it
separates $x$ and $y$.  
Thus the intersection point $z'$ between $[x,y]$ and $\ell_{z,p}$ belongs to $R(p)$.
Recall that Proposition~\ref{CirculosEnSegmento} implies that $C(z')$ is a separating circle.
%Additionally observe that $z', z, p$ are collinear and that $d(z',p)$ and $d(z,p)$ define the radius of $C(z')$ and $C(z)$ respectively, 
%therefore $C(z)\subseteq C(z')$.
Trivially, $C(z)\subseteq C(z')$ since the latter is obtained by expanding $C(z)$ while anchoring it to $z$.
Since $C(z)$ is a $P$-circle contained inside a separating circle, by
Observation~\ref{Relation P-circle separating circle} $C(z)$ is also a separating circle. 
\end{proof}

%%%%%%%%%%%%%%%%%%%%%%%%%Ejemplos
\begin{figure}[h]
\begin{center}
\includegraphics{img/CommonAncestor.pdf}
\caption{\small Illustration for  Lemma~\ref{Common Ancestor}.} 
\label{fig:CommonAncestor}
\end{center}
\end{figure}


The following is also proved in~\cite{DynamicCircleSeparability}.
\begin{theorem}\label{sep in T_s}
Let $s$ be a point on $\mathcal{V}(P)$. If $s$ is a separating point, 
then $\sep$  belongs to $T_s$.
\end{theorem}
\begin{proof}
Suppose that $\sep$ does not belong to $T_s$.
Let $z$ be the lowest common ancestor of $\sep$ and $s$.
Lemma~\ref{Common Ancestor} implies that $C(z)$ is a separating circle 
and 
%since $z$ is an ancestor of $\sep$, Proposition~\ref{Rho is monotonic} implies
 that $\rho(z)< \rho(\sep)$ which is a contradiction.
\end{proof}

Given a separating point $s$,
we claim that if we move a point $y$ continuously from $s$ towards $\cp$ on $T_s$, 
then $C(y)$ will shrink and approach $Q$, 
becoming tangent to it for the first time when $y$ reaches $\sep$. To prove our claim in Lemma~\ref{TangentToQ}, we introduce the following notation. 

Let $x$ be a point lying on an edge $e$ of $\mathcal{V}(P)$ such that $e$ lies on the bisector of $p,p'\in P$. Let $C^-(x)$ and $C^+(x)$ be the two closed convex regions obtained by splitting the disk $C(x)$ with the segment  $[p,p']$. Assume that $x$ is contained in $C^-(x)$.

\begin{observation}\label{obs:PushingCircles}
Let $x,y$ be two points lying on an edge $e$ of $\mathcal{V}(P)$.
If $\rho(x) > \rho(y)$, then $C^+(x)\subset C^+(y)$ and $C^-(y)\subset C^-(x)$.
\end{observation}

%%%%%%%%%%%%%%%%%%%%%%%%%Ejemplos
\begin{figure}[h!]
\begin{center}
\includegraphics[width=75mm]{img/PushingCircles.pdf}
\caption{\small The result of Observation~\ref{obs:PushingCircles} when $\rho(x) > \rho(y)$.} 
\label{fig:PushingCircles}
\end{center}
\end{figure}

Using this simple observation that can be seen in Figure~\ref{fig:PushingCircles}, we obtain the following generalization.

\begin{proposition}\label{prop:PushingCricles}
Let $s$ be a point on $\mathcal{V}(P)$ and let $x$ and $y$ be two points  on $T_s$. If $\rho(x) > \rho(y)$, then $C^+(x)\subset C^+(y)$ and $C^-(y)\subset C^-(x)$.
\end{proposition}
\begin{proof}
Note that if $x$ and $y$ lie on the same edge, then the result holds by Observation~\ref{obs:PushingCircles}. 
If they are on different edges, we consider the path $\Phi = (x,  v_0, \ldots,  v_k, y)$ contained in $T_s$ joining $x$ and $y$, such that $v_i$ is a vertex of $\mathcal{V}(P)$, $i\in \{0, \ldots, k\}$. 
Thus, Observation~\ref{obs:PushingCircles} and Proposition~\ref{Rho is monotonic} imply that $C^+(x)\subset C^+(v_0)\subset \ldots \subset C^+(v_k)\subset C^+(y)$ and that $C^-(y)\subset C^-(v_k)\subset \ldots \subset C^-(v_0)\subset C^-(x)$.
\end{proof}


Note that $\Sep = C(\sep)$ must intersect $Q$. Otherwise, we could always push $\sep$ closer to the root on $\mathcal{V}(P)$, while keeping it as a separating point. 
Furthermore, since $Q$ is convex and $\Sep$ contains no point of $Q$ in its interior, 
the intersection consists on only one point.
From now on we refer to $\tang$ as the tangency point between $\Sep$ and $Q$.

We claim that $\tang$ lies on the boundary of $C^+(\sep)$. 
Assume to the opposite that $\tang$ lies on $C^-(\sep)$.  
Let $\varepsilon>0$ and let $c_\varepsilon$ be the point obtained by moving $\sep$ a $\varepsilon$ distance towards to $\cp$ on $\mathcal{V}(P)$. 
Note that by Proposition~\ref{Rho is monotonic}, $\rho(c_\varepsilon) < \rho(\sep)$. 
In addition, Proposition~\ref{prop:PushingCricles} implies that $C^-(c_\varepsilon)\subset C^-(\sep)$. 
Since we assumed that $\tang$ lies on the boundary of $C^-(\sep)$, we conclude that $\tang$ does not belong to $C(c_\varepsilon)$.
This implies that, for $\varepsilon$ sufficiently small, $C(c_\varepsilon)$ is a separating circle which is a contradiction to the minimality of $\Sep$.

\begin{lemma}\label{TangentToQ}
Let $s$ be a separating point. 
If $x$ is a point lying on $T_s$, then $C(x)$ is a separating circle if and only if $\rho(x) \geq \rho(\sep)$.
Moreover, $\Sep$ is the only separating circle that intersects $Q$.
\end{lemma}

\begin{proof}
Let $s$ be a separating point. We know by Theorem~\ref{sep in T_s} that $\sep$ belongs to $T_s$.
Let $x_1$ and $x_2$ be two points on $T_s$ such that  $\rho(x_1) < \rho(\sep)$ and  $\rho(\sep) < \rho(x_2)$.
Proposition~\ref{prop:PushingCricles} implies that $C^+(\sep)\subset C^+(x_1)$ and since $\tang$ belongs to the boundary of $C^+(\sep)$, 
we conclude $C(x_1)$ contains $\tang$ in its interior. Therefore $C(x_1)$ is not a separating circle.

On the other hand, $C(x_2)$ contains no point of $Q$. Otherwise, let $q\in Q$ be a point lying on $C(x_2)$. 
Two cases arise:
Either $q$ belongs to $C^-(x_2)$ or $q$ belongs to $C^+(x_2)$. In the former case, since $\rho(s) > \rho(x_2)$, $q\in C^-(x_2)\subset C^-(s)$--- a contradiction since $C(s)$ is a separating circle. 
In the latter case, since $\rho(x_2) > \rho(\sep)$, Proposition~\ref{prop:PushingCricles} would imply that $q$ belongs to the interior of $\Sep$ which would also be a contradiction.
\end{proof}

\section{The algorithm}%%%
The basis of our algorithm is to find a separating point $s$ and from there, perform a binary search on $T_s$ to find a separating circle tangent to $Q$ with center on this path.  
This is a rather intuitive solution, which was also used in~\cite{DynamicCircleSeparability}.  
However we use some additional geometric properties to reduce the time complexity.

\subsection{Preprocessing}%%%%%
We first compute $\mathcal{V}(P)$ and $\cp$ in 
$O(n \log n)$ time~\cite{shamos}.
$\mathcal{V}(P)$ can be stored as a binary tree  with $n$ (unbounded) leaves, 
so that every edge and every vertex of the tree has a set of pointers to the vertices of $P$ defining it.
Every Voronoi region is stored as a convex polygon and
 every vertex $p$ of $P$ has a pointer to $R(p)$.
%Additionally we compute the minimum $P$-circle $\CP$ along with its center $\cp$ in linear time~\cite{LinearTimeAlgorithmsForLinearProgramming}.\greg{we don't need this, we get it in log time after computing the diagram.  should be  part of the citation for nlogn}
If $\cp$ is not a vertex of $\mathcal{V}(P)$, 
we split the edge that it belongs to.

We want our data structure to support binary search queries on any possible path $T_s$ of $\mathcal{V}(P)$.
To do this, we will use an operation on the vertices of $\mathcal{V}(P)$ called $\textsc{FindMidPoint}$ with the following property. 
Given two vertices $u,v$ in $T_s$, $\textsc{FindMidPoint}(u,v)$ returns a vertex $z$
that splits the path on $T_s$ joining $u$ and $v$ into two subpaths, each containing
a constant fraction of the  vertices.
Several data structures exist, that can be constructed in $O(n\log n)$ time using linear space, which support this operation in $O(1)$ time~\cite{ConstrainedMinimumEnclosingCircleWithCenterOnAQueryLineSegment}{\red \cite{}\cite{}}. \luis{Maybe Stefan has some extra references to these data structures, light and heavy path decomposition for example}.
% Assume from now on that the data structure on $\mathcal{V}(P)$ has been computed and that our operations has been implemented.

%%%%%%%%%%%%%%%%%%%%%%%%%


\subsection{Searching for $\sep$ on the tree}
Recall that if $\CP$ is  a separating circle then it is a trivial solution.  
Since $Q$ is a convex $m$-gon, this can be checked easily in $O(\log m)$ time~\cite{ComputingExtremeDistancesBetweenConvexPolygons}. 
% by computing the distance between $\cp$ and $Q$
%If this distance is greater than the radius of $\CP$, then $\CP$ is the minimum separating circle.
Thus we will assume that $\CP$ is not the minimum separating circle, 
which implies that $\CP$ intersects $Q$.

To determine the position of $\sep$ on $\mathcal{V}(P)$, we
first  find a separating point $s$ and then
 search for $\sep$ on $T_s$ using our data structure.

To find $s$, we construct a separating line $L$ between $P$ and $Q$. 
This can be done in $O(\log n + \log m)$ time~\cite{ComputingExtremeDistancesBetweenConvexPolygons}.
Let $p_{_L}$ be the point  closest  to $L$ and assume that no other point in $P$ lies at the same distance; otherwise rotate $L$ slightly.
%keeping $P$ and $Q$ separated by $L$. 
Let $L_{\perp}$ be the perpendicular to $L$ that contains $p_{_L}$ and let $s$ be the intersection 
%(unique, by construction) 
of $L_{\perp}$ with the boundary of $R(p_{_L})$; see Figure~\ref{fig:PrimerCirculoSeparador}.
We know that  $L_\perp$ intersects $R(p_{_L})$ because 
 $L$ can be considered as a $P$-circle, containing only $p_{_L}$, with center at infinity  on $L_\perp$.
%Thus if we let $z$ be a point on $L_\perp$ sufficiently far away such that $C(z)$ looks like $L$ in the vicinity of $P$ and $Q$, 
%then $C(z)$ will be a separating circle and the farthest point of $P$ from $z$ will be $p_{_L}$.
%This implies that $z$ will belong to $R(p_{_L})$ and therefore $s$ is well defined.


\begin{figure}[h!]
\begin{center}
\includegraphics[width=65mm]{img/ConstruccionS_0.pdf}
\caption{\small Construction of $s$.} 
\label{fig:PrimerCirculoSeparador}
\end{center}
\end{figure}


Since $s$ is on the boundary of $R(p_{_L})$,  $C(s)$ passes through $p_{_L}$. Furthermore $C(s)$ is contained on the same halfplane defined by $L$ that contains $P$. 
% and one other point of $P$ on its boundary, and all other points of $P$ within.
%Note that $d(s,p_{_L})$ defines the radius of $C(s)$, hence $C(s)$ is contained on the same halfplane defined by $L$ that contains $P$. 
So $C(s)$ is a separating circle.
% and that $s$ lies on an edge of $\mathcal{V}(P)$; see again Figure~\ref{fig:PrimerCirculoSeparador}. 
Assume that $s$ lies on the edge $\overline{xy}$ of $\mathcal{V}(P)$ with $\rho(x) > \rho(y)$ and 
let $T_{s} = ( u_0 = s, u_1 = y, \ldots, u_r = \cp)$ be the path of length $r+1$ joining $s$ with $\cp$ in $\mathcal{V}(P)$. Theorem~\ref{sep in T_s} implies that $\sep$ lies on $T_s$.\\

It is possible to use our data structure to perform a binary search on the vertices of $T_s$, computing, at each vertex $v$, the distance to $Q$ and the radius of $C(v)$. This way we could determine if $C(v)$ is a separating (or intersecting) circle.
% and hence, we could proceed with the search by removing a linear fraction of the vertices of $T_s$ at each step. 
However, this approach involves computing the distance to $Q$ at each step in $O(\log m)$ time, and thus takes  $O(\log n\cdot\log m)$ time.  This was the algorithm given in~\cite{DynamicCircleSeparability}.

It is worth noting that if the distance to our query object can be computed in $O(1)$ time, 
then the described algorithm takes $O(\log n)$ time. This is the case when instead of being an $m$-gon, $Q$ is either a circle or a point.

\begin{corollary}\label{corollary:ResultForCircleAndPoints}
After preprocessing a set $P$ of $n$ points in $O(n \log n)$ time,
the minimum separating circle between $P$ and any given circle or point
can be found in $O(\log n)$ time.
\end{corollary}

In the case of $Q$ being a convex $m$-gon, an improvement from the $O(\log n \log m)$ time algorithm can be obtained by strongly using the convexity of $Q$.

%Note that we only need to know if $C(v)$ intersects $Q$ to decide if it is a separating circle.
To determine if some point $v$ on $T_s$ is a separating point, it is not always necessary to
%However, we will not 
compute the distance between $v$ and $Q$.
% to do that, but the 
One can first test, in constant time, if $C(v)$ intersects a  separating line tangent to $Q$.
%, which can be done in constant time. 
%This way if $C(v)$ does not intersect the separating line, we conclude that $C(v)$ is a separating circle and our binary search could continue.
If it does not intersect it, we can proceed with the binary search since $C(v)$ would be a separating circle.
Otherwise, we can try to compute a new separating line tangent to $Q$ not intersecting $C(v)$.
The advantage of this is that while doing so, we reduce the portion of $Q$ that we need to consider in the future.
This is done as follows.

%%%%%%%%%%%%%%%%%%%%%%%%%


Compute the two internal tangents $L, L'$ between $C(s)$ and $Q$ in $O(\log m)$ time.
\luis{~\cite{godfried} I think that this reference is wrong, Godfried et al. showed how to compute the internal tangents between two polygons but in $O(n)$ time and we need logarithmic and between a convex polygon and a circle. 
This is in fact an exercise from a computational geometry class and I think that no reference is available}.
Let $q$ and $q'$ be the respective tangency points of $L$ and $L'$ with the boundary of $Q$. 
In Figure~\ref{fig:q equal to q'} we  see an example where $q$ and $q'$ are the same vertex. In this case it is easy to see that the minimum separating circle must be tangent to $Q$ at $q=q'$.
Thus we can forget about $Q$ and compute the minimum separating circle between $P$ and $q$.
%, we will obtain the same separating circle. 
%Therefore, since computing the distance to $q$ requires $O(1)$ time, we can perform a search on $T_s$ for the edge containing $\sep$ 
As mentioned previously in Corollary~\ref{corollary:ResultForCircleAndPoints} this takes  $O(\log n)$ time.

%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{figure}[h!]
\begin{center}
\includegraphics[width=58mm]{img/qq'Equal.pdf}
\caption{\small The two tangents $L$ and $L'$ intersect $Q$ at the same point, $q$. The minimum separating circle $\Sep$ passes through $q$.} 
\label{fig:q equal to q'}
\end{center}
\end{figure}



%If they are not unique, rotate $L$ and $L'$ slightly keeping them tangent to $Q$ and so that $C(s)$ and $Q$ remain separated; see Figure~\ref{fig:InternalTangents}(a).
%%%%%%%  were we looking for unique lines?   what does that mean? 


Assume from now on that $q\neq q'$, as shown 
in  Figure~\ref{fig:InternalTangents}(a).
 We will consider the clockwise polygonal chain $\varphi = [q = q_0, \ldots, q_k = q']$
 %, lying inside the convex hull of $P\cup Q$, 
 joining $q$ and $q'$; see Figure~\ref{fig:InternalTangents}(b). 

 %Assume that this chain is sorted along the boundary of $Q$ in clockwise order; see Figure~\ref{fig:InternalTangents}(b). 
 
 \begin{figure}[h!]
\begin{center}
\includegraphics[width=120mm]{img/InternalTangents.pdf}
\caption{\small (a) The case where $q\neq q'$;  (b) Construction of $\varphi$.} 
\label{fig:InternalTangents}
\end{center}
\end{figure}

Let $\tang$ be the tangency point between $\Sep$ and $Q$. 
It is clear that $\tang$ lies on an edge of $\varphi$ since
% the tangent to $\Sep$ passing through $\tang$ is a separating line, and for every point on the boundary 
no separating line passes through any other boundary point on $Q$.
%, not in $\varphi$, there is no such separating line.

For each edge $e_i = q_iq_{i+1}$  ($0\leq i\leq k-1$) of $\varphi$, let $\ell_i$ be the line extending that edge. Each $\ell_i$ separates  $Q$ and $P$. We say that a point $x$ on $\ell_i$ but not in $e_i$ lies to the left of $e_i$ if it is closer to $q_i$, or to the right if it is closer to $q_{i+1}$.

Our algorithm will essentially perform two parallel binary searches, the first one on $T_s$ and the second one on $\varphi$, such that at each step we discard either a linear fraction of $T_s$ or a linear fraction of $\varphi$.   As we search on $T_s$, every time we find a separating circle, we move towards $\cp$.
When we confirm that a $P$-circle intersects $Q$ we move away from $\cp$.
As mentioned, we attempt to confirm if the current vertex $v$ being checked corresponds to a separating point by comparing $C(v)$ to some separating line $\ell_i$, i.e., in constant time. If they don't intersect, we instantly discard half of the path on $\mathcal{V}(P)$.  In fact, as we do this, we also make another quick attempt to check if $C(v)$ intersects $Q$.  If so,  then again we can proceed with the binary search on $T_s$.  This test is done by comparing $C(v)$ and the edge $e_i$ for intersection.
If neither of our  attempts succeed,  we are not able to quickly conclude whether $C(v)$ intersects $Q$ or not.  Thus we suspend the binary search on  $\mathcal{V}(P)$ and focus on $C(v)$,  using it to eliminate half of $\varphi$.   Specifically, the fact that $C(v)$ intersects $\ell_i$ to one side of $e_i$  tells us that no
future $P$-circle on our search will intersect  $\ell_i$ to the other side of $e_i$. This implicitly discards half of $\varphi$ from future consideration, and is discussed in more detail in the Theorem that follows.    Thus, in constant time, we manage to remove half of the path on  $\mathcal{V}(P)$, or half of $\varphi$, which will give the desired time bound.
The entire process is detailed in Algorithm~\ref{alg:DualBinarySearch}. 

\begin{algorithm}
\caption{Given $T_{s} = ( u_0 = s, u_1 = y, \ldots, u_r = \cp)$ and $\varphi = [q = q_0, \ldots, q_k = q']$,  find the edge of $T_s$ containing $\sep$}
\begin{algorithmic}[1]\label{alg:DualBinarySearch}
	\STATE Define the endpoints of the subpath of $T_s$ containing $\sep$, $u\gets s, v\gets \cp$
	\STATE Define the initial search interval on $\varphi$, $a\gets 0, b\gets k$
	\IF{$u$ and $v$ are consecutive vertices and $b= a+1$}\label{alg:MoveOn}
		\STATE End and return the segment $S=[u,v]$ and the segment $H = [q_a, q_b]$
	\ENDIF
	\STATE Let $z\gets \textsc{FindMidPoint}(u,v)$,  $j\gets \lfloor \frac{a+b}{2}\rfloor$ 	
	\STATE Let $e_j \gets \overline{q_j q_{j+1}}$ and let $\ell_j$ be the line extending $e_j$
	\IF{$b > a+1$} \label{alg:comparison}
		\STATE Compute $\rho(z)$ and 
		let $\delta \gets d(z, \ell_j)$, $\Delta\gets d(z, e_j)$
	\ELSE
		\STATE Compute $\rho(z)$ and let $\delta \gets d(z, e_j)$, $\Delta \gets d(z, e_j)$
	\ENDIF
	\IF{$\rho(z) \leq \delta$, that is $C(z)$ is a separating circle}
		\STATE Move forward on $T_s$, 
		$u\gets z$ and return to step~\ref{alg:MoveOn} \label{alg:redefine_u}
	\ELSE
		\IF{$\rho(z) > \Delta$ , that is if $C(z)$ is not a separating circle}
			\STATE Move backward on $T_s$, 
			$v\gets z$ and return to step~\ref{alg:MoveOn}  \label{alg:redefine_v}
		\ELSE
			\IF{$C(z)$ intersects $\ell_j$ to the left of $e_j$}
				\STATE We discard the polygonal chain to the right of $e_j$, 
				$b \gets \max\{j, a+1\}$  \label{alg:redefine_b}
			\ELSE
				\STATE We discard the polygonal chain to the left of $e_j$, 
				$a \gets j$   \label{alg:redefine_a}
			\ENDIF
			\STATE Return to step~\ref{alg:MoveOn}
		\ENDIF
	\ENDIF
\end{algorithmic}
\end{algorithm}
%\newpage

\begin{theorem}
Algorithm~\ref{alg:DualBinarySearch} finds the edge of $T_s$ containing $\sep$ in $O(\log n + \log m)$ time.
\end{theorem}
\begin{proof}
Our algorithm maintains two invariants.
The first  is that $C(u)$ is never a separating circle and $C(v)$ is always a separating circle. 
To begin with, $C(u) = C(s)$ is a separating circle, while
 $C(v) = \CP$ is not a separating circle. If either of these assumptions does not hold, the problem is solved trivially, without resorting to this algorithm.
Changes to $u$ and $v$ occur in steps~\ref{alg:redefine_u} or~\ref{alg:redefine_v}, and in both cases the invariant is preserved. Thus, $\sep$ always lies on the path joining $u$ with $v$.

The second invariant is that $\tang$, the tangency point between $\Sep$ and $Q$, 
always lies on the clockwise path joining $q_a$ with $q_b$ along $\varphi$. We already explained that the invariant holds when $a=0$ and $b=k$, corresponding to the inner tangents supporting $P$ and $Q$.
Thus we only need to look at steps~\ref{alg:redefine_b} and~\ref{alg:redefine_a}, where $a$ and $b$ are redefined. 

We will analyze step~\ref{alg:redefine_b}, however step~\ref{alg:redefine_a} is analogous. 
In step~\ref{alg:redefine_b} we know that $C(z)$ intersects $\ell_j$ to the left of $e_j$ and that $e_j$ does not intersect $C(z)$.
We claim that for every point $w$ lying on an edge of $T_s$, if $C(w)$ is a separating circle, then $C(w)$ intersects $\ell_j$ to the left of $e_j$. Note that if our claim is true, we can forget about the polygonal chain lying to the right of $e_j$ since no separating circle (nor a separating line) will intersect it. \greg{including tangents}
To prove our claim, suppose that there is a point $w$ on $T_s$, such that $C(w)$ is a separating circle and $C(w)$ intersects $\ell_j$ to the right of $e_j$. 
Let $x$ and $x'$ be  two points on the intersection of $\ell_j$ with  $C(w)$ and $C(z)$, respectively.
Suppose first that $\rho(w)<\rho(z)$ and recall that by Proposition~\ref{prop:PushingCricles}, since $x'$ lies on $C^+(z)\subset C^+(w)$, $x'$ lies in $C(w)$. 
Thus, both $x$ and $x'$ belong to $C(w)$ which by convexity implies that $e_j$ is contained in $C(w)$. Therefore $C(w)$ is not a separating circle which is a contradiction.
Analogously, if $\rho(w) > \rho(z)$, then $e_j$ is contained in $C(z)$ which is directly a contradiction since we assumed the opposite; our claim holds.\\

Note that in each iteration of the algorithm, $a,b,u$ or $v$ are redefined so that either a linear fraction of $\varphi$ or a linear fraction of $T_s$ is discarded. Thus the algorithm finishes in $O(\log n + \log m)$ iterations. 

One extra detail needs to be considered when $b = a+1$. In this case only one edge $e = [q_a, q_{a+1}]$ remains from $\varphi$, and $\tang$ lies on that edge. Thus, if the line $\ell$ extending $e$ intersects $C(z)$ but $e$ does not, then either step \ref{alg:redefine_b} or \ref{alg:redefine_a} is executed. However, nothing will change in these steps and the algorithm will loop.
In order to avoid that, we check in step~\ref{alg:comparison} if only one edge $e$ of $\varphi$ remains. 
If this is the case, we know by our invariant that $\tang$ belongs to that edge and therefore we continue the search computing the distance to $e$ instead of computing the distance to the line extending it.
This way, the search on $\varphi$ stops but it continues on $T_s$ until the edge of $\mathcal{V}(P)$ containing $\sep$ is found.

Since we ensured  that every edge in $\mathcal{V}(P)$ has pointers to the points in $P$ that defined it, every step in the algorithm can be executed in $O(1)$ time. Thus, we conclude that Algorithm~\ref{alg:DualBinarySearch} finishes in $O(\log n + \log m)$ time. 

Since both invariants are preserved during the execution, Lemma~\ref{TangentToQ} implies that the algorithm returns segments $[u, v]$ from $T_s$ containing $\sep$, and $[q_a, q_{b}]$ from $\varphi$ containing $\tang$.
\end{proof}

From the output of Algorithm~\ref{alg:DualBinarySearch} it is trivial to obtain $\sep$ in constant time,
so we conclude the following.
%Let $S$ and $H$ be the segments returned by Algorithm~\ref{alg:DualBinarySearch}, and assume that $S$ is a segment lying on the bisector of the points $p_0, p_1\in P$.When the algorithm finishes, our problem is reduced to that of finding a point $\sep$ in the segment $S$ such that $d(\sep, p_0) = d(\sep,H)$. Therefore since $S$ and $H$ are line segments, this problem can be solved
% with a quadratic equation  in constant time, and we conclude the following.

\begin{corollary}
After preprocessing a set $P$ of $n$ points in $O(n \log n)$ time,
% to construct a data structure of size $O(n)$ that supports the \textsc{FindMidPoint} operation in $\mathcal{V}(P)$.
the minimum separating circle between $P$ and any query convex $m$-gon
% $Q$ 
can be found in $O(\log n + \log m)$ time.
\end{corollary}



\begin{thebibliography}{4}

\bibitem{Aggarwal:1985}
A. Aggarwal,  H. Booth, J. O'Rourke, S. Suri and C.K. Yap, Finding minimal convex nested polygons,
\emph{Proceedings of the first annual symposium on Computational geometry} (1985), 296--304.
%@article{abosy-fmcnp-89
%, author =	"A. Aggarwal and H. Booth and Joseph O'Rourke and Subhash Suri and C. K. Yap"
%, title =	"Finding minimal convex nested polygons"
%, journal =	"Inform. Comput."
%, volume =	83
%, number =	1
%, month =	oct
%, year =	1989
%, pages =	"98--110"
%, keywords =	"packing, visibility, convex polygons, extremal figures"
%, succeeds =	"abosy-fmcnp-85"
%, update =	"98.03 mitchell, 95.05 korneenko"
%}

\bibitem{LinearVoronoiDiagramForConvexPolygon}
A. Aggarwal, L.J. Guibas, J. Saxe and P.W. Shor, A linear-time algorithm for computing the Voronoi diagram of a convex polygon,
\emph{Discrete Comput. Geom.} (1989), 4:591--604.

\bibitem{augustine-etal}
J. Augustine, S. Das, A. Maheshwari, S.C. Nandy, S. Roy and S. Sarvattomananda,
Localized geometric query problems,
\emph{arXiv:1111.2918} (2011)

\bibitem{DynamicCircleSeparability}
L. Barba and J. Urrutia, Dynamic circle separability between convex polygons
\emph{XIV Spanish Meeting on Computational Geometry} (2011), 43--46.

\bibitem{ComputingCircularSeparabilityOfPlanarPointSets}
B. K. Bhattacharya, Circular separability of planar point sets, 
\emph{Computational Morphology} (1988), 25--39.

\bibitem{boissonat-etal}
J-D. Boissonat, J. Czyzowicz, O. Devillers and M. Yvinec, Circular separability of polygons,
\emph{Algorithmica} (2001), 30:67--82.


\bibitem{DasJoseph:1990}
G. Das and D. Joseph, The complexity of minimum convex nested polyhedra,
\emph{In Proc. 2nd Canad. Conf. Comput. Geom.} (1990), 296--301.

\bibitem{8people}
E. Demaine, J. Erickson, F. Hurtado, J. Iacono, S. Langerman, H. Meijer, M. Overmars and S. Whitesides,
Separating point sets in polygonal environments,
\emph{Proc. 20th Annual ACM Symposium on Computational Geometry (SoCG)} (2004), 10--16.

\bibitem{ComputingExtremeDistancesBetweenConvexPolygons}
H. Edelsbrunner, Computing the extreme distances between two convex polygons, 
\emph{Journal of Algorithms} (1985), 6:213--224.		

\bibitem{MinimumPolygonalSeparation}
H. Edelsbrunner and F.P. Preparata, Minimum polygonal separation, 
\emph{Inform. Comput.} (1988), 77:218--232.

\bibitem{SeparatingPointsByCricles}
S. Fisk, Separating points by circles and the recognition of digital discs, 
\emph{IEEE Trans. Pattern Anal. Mach. Intell.} (1986), 8(4):554--556.

\bibitem{DigitalDiskAndCompacness}
C. E. Kim and T. A. Anderson, Digital disks and a digital compactness measure,
\emph{STOC '84: Proceedings of the Sixteenth Annual ACM Symposium on Theory of Computing}, (1984), 117--124.

\bibitem{SeparationBySphericalSurfaces}
S.R. Lay, On separation by spherical surfaces, 
\emph{Amer. Math. Monthly} \textbf{1} (1971), 78:1112--1113.


%\bibitem{LinearTimeAlgorithmsForLinearProgramming}
%N. Megiddo, Linear-Time Algorithms for Linear Programming in $R^3 $ and Related Problems, 
%\emph{SIAM Journal on Computing} \textbf{12} (1983), 759--776.

\bibitem{LinearProgrammingInLinearTime}
N. Megiddo, Linear programming in linear time when the dimension is fixed, 
\emph{J. ACM}  (1984), 31:114--127.

\bibitem{ComputingCircularSeparability}
J. O'Rourke, S.R. Kosaraju and N. Megiddo, Computing circular separability, 
\emph{Discrete and Computational Geometry} \textbf{1} (1986), 105--113.


\bibitem{ConstrainedMinimumEnclosingCircleWithCenterOnAQueryLineSegment}
S. Roy, A. Karmakar, S. Das and S.C. Nandy, Constrained minimum enclosing circle with center on a query line segment,
\emph{Computational Geometry} (2009), 42:632--638.

\bibitem{shamos}
M.I. Shamos and D. Hoey, Closest point problems,
\emph{in Proceedings of 16th Annual IEEE Symposium on Foundations of Computer Science},  (1975), 151--162.

\bibitem{SO}
S. Suri and J. O'Rourke, Finding minimal nested polygons,
\emph{Proc. 23rd Allerton Conf. Commun. Control Comput.} (1985), 470--479.

\bibitem{godfried}
G.T. Toussaint, Solving geometric problems with the rotating calipers,
\emph{Proceedings of IEEE MELECON'83, Athens, Greece} (1983).

\bibitem{Wang}
C. Wang, Finding minimal nested polygons,
\emph{BIT Numerical Mathematics} (1991) 31(2):230--236.

\bibitem{WangChan}
C. Wang and E.P.F.  Chang, Finding the minimum visible vertex distance between two non-intersecting simple polygons,
\emph{Proceedings of the second annual symposium on computational geometry (SoCG)} (1986),
34--42.



\end{thebibliography}

\end{document}
